package summary;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/11 11:54
 * https://leetcode-cn.com/problems/partition-equal-subset-sum/
 */
public class Title416 {

    /**
     * 0-1背包问题
     * dp[i]表示容量为i的背包从物品中选择的最大价值
     * 递推公式：dp[i] = Math.max(dp[i], dp[i-nums[i]] + nums[i])
     * 初始化：dp[0] = 0
     * @param nums
     * @return
     */
    public static boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        int[] dp = new int[target + 1];
        dp[0] = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[target] == target;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,5};
        canPartition(arr);
    }
}
